// 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
// 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
// 来源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/longest-palindromic-subsequence
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
  const len = s.length
  const dp = new Array(len).fill(0).map(() => new Array(len).fill(0))

  for (let i = 0; i < len; i++) {
    dp[i][i] = 1
  }


  for (let i = len - 2; i >= 0; i--) {
    for (let j = i + 1; j < len; j++) {
      let p1 = 0
      if (s[i] === s[j]) {
        p1 = dp[i + 1][j - 1] + 2
      }
      const p2 = dp[i + 1][j]
      const p3 = dp[i][j - 1]

      dp[i][j] = Math.max(p1, p2, p3)
    }
  }

  return dp[0][len - 1]
}

console.log(
  longestPalindromeSubseq('bbbab')
)
